package com.topcoder.srm200;

import java.util.ArrayDeque;

public class Graduation {
	int N;
	int M = 128;
	int[] cls;
	int[][] req;
	int[] edge;
	int total = 0;
	
	public String moreClasses(String classesTaken, String[] requirements) {
		N = requirements.length;
		cls = new int[M];
		req = new int[N][M];
		edge = new int[N];
		
		for (int i=0; i<M; i++) cls[i] = -2;
		for (int i=0; i<N; i++) {
			for (char c : requirements[i].toCharArray()) {
				if (c >= '0' && c <= '9') {
					edge[i] = edge[i]*10 + (c - '0');
				}
				else {
					req[i][c] = 1;
					cls[c] = -1;
				}
			}
			total += edge[i];
		}
		
		for (char c : classesTaken.toCharArray()) {
			findPath(c);
		}
		
		if (total == 0) return "";
		StringBuilder sb = new StringBuilder();
		
		for (char i=0; i<M; i++) {
			if (findPath(i)) sb.append(i);
			if (total == 0) return sb.toString();
		}
		
		return "0";
	}
	
	private boolean findPath(char i) {
		if (cls[i] != -1) return false;
		ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
		queue.add((int)i);
		int[] from = new int[M];
		for (int j=0; j<M; j++) from[j] = -1;
		
		while (!queue.isEmpty()) {
			int current = queue.remove();
			for (int j=0; j<N; j++) {
				if (req[j][current]==1 && edge[j]>0) {
					edge[j]--;
					while (current >= 0) {
						req[j][current] = -1;
						cls[current] = j;
						current = from[current];
					}
					total--;
					return true;
				}
			}
			
			for (int j=0; j<N; j++) {
				if (req[j][current] > 0) {
					for (int k=0; k<M; k++) {
						if (req[j][k] < 0 && from[k] < 0) {
							from[k] = current;
							queue.add(k);
						}
					}
				}
			}
		}
		
		return false;
	}
}
